/*
 * @lc app=leetcode.cn id=20 lang=javascript
 *
 * [20] 有效的括号
 */

// @lc code=start
/**
 * @param {string} 
 * @return {boolean}
 */
/* 个人分析： 如果这是一个闭合括号字符串（ 前提字符串为偶数）， 那么每一个左右括号都能配对成功，那么我们就以左括号为主，如果左括号都能被右括号正确配对，则确认为闭合括号字符串；
从而我们要从头遍历字符串， 遇到左括号我们就先放入一个数组里面， 遇到右括号就与数组最后一个
左括号对比， 如果匹配成功， 则消除对应左括号， 一直循环， 知道数组为空， 说明括号都已经闭合， 那么可以确定为闭合括号字符串
为什么要用栈呢： 1. 因为遇到左括号也是往数组最后添加；
2. 遇到右括号一定是与数组最后一个左括号进行匹配的（ 原因是位置要对应）， 从而判断是否删除数组里面的最后一个左括号；
3. 上述操作都是对数组末尾元素进行操作， 类比为就是对栈的顶端进行操作， 所以用栈来解这道算法题 */
// 思路：1.判断字符串长度是否为偶数，如果为奇数，直接返回false；
// 2.创建的Map类，用来匹配相应的左右括号；
// 3.创建一个stack数组，用来存放左括号；
// 4.遍历字符串，遇见左括号入栈，遇见右括号则与stack顶端左括号对比，如果比配成功，则左括号进行出栈操作；否则，直接返回false；
// 5.遍历结束，如果stack的长度为0，说明左右括号已经全部配对完成，返回true；
let isValid = function (s) {
    if (s.length % 2 !== 0) {
        return false;
    }
    let map = new Map();
    map.set("{", "}").set("(", ")").set("[", "]");
    let stack = [];
    for (let i in s) {
        //遇见左括号
        if (map.has(s[i])) {
            stack.push(s[i]);
        } else { //遇见右括号,pop()会返回数组最后一个元素
            if (map.get(stack.pop()) !== s[i]) {
                return false;
            }
        }
    }
    if (stack.length !== 0) {
        return false;
    }
    return true;
}
// @lc code=end